package com.hspedu.newData.dmsxl.动态规划.背包问题;

import org.junit.Test;

/**
 * @Author: yh
 * @description: 
 * @CreateTime: 2025-05-06 
 * @Version: 1.0
 */

public class LC1049最后一块石头的重量Ⅱ {

    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int stone : stones) {
            sum += stone;
        }

        int target = sum/2;
        int len = stones.length;
        boolean[][] dp = new boolean[len][target+1];

        if (stones[0] <= target){
            dp[0][stones[0]] = true;
        }

        for (int i = 1; i < len; i++) {
            for (int j = 0; j <= target; j++) {
                dp[i][j] = dp[i-1][j];

                if (stones[i] == j){
                    dp[i][j] = true;
                    continue;
                }
                if (stones[i] < j){
                    dp[i][j] = dp[i-1][j] || dp[i-1][j-stones[i]];
                }
            }
        }

        for (int i = target; i > 0; i--) {
            if (dp[len-1][i]){
                return sum - 2*i;
            }
        }
        return -1;
    }


    @Test
    public void test() {
        // 测试代码

//        int i = lastStoneWeightII(new int[]{2,7,4,1,8,1});
//        int j = lastStoneWeightII(new int[]{31,26,33,21,40});
        int j = lastStoneWeightII(new int[]{1,2});
        System.out.println("----");
    }
}
